package com.klun.project.common.constans.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。
// 请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]]
// （若两个四元组元素一一对应，则认为两个四元组重复）：
// 0 <= a, b, c, d < n
// a、b、c 和 d 互不相同
// nums[a] + nums[b] + nums[c] + nums[d] == target
// 你可以按 任意顺序 返回答案 。
// 示例 1：
//输入：nums = [1,0,-1,0,-2,2], target = 0
//输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
// 示例 2：
//输入：nums = [2,2,2,2,2], target = 8
//输出：[[2,2,2,2]]
// 提示：
// 1 <= nums.length <= 200
// -109 <= nums[i] <= 109
// -109 <= target <= 109
// Related Topics 数组 双指针 排序
// 👍 1422 👎 0

public class Solution18 {

	public List<List<Integer>> fourSum(int[] nums, int target) {
		List<List<Integer>> ans = new ArrayList<>();
		Arrays.sort(nums);
		int len = nums.length;
		int a;
		int b;
		int c = len - 1;
		for (int i = 0; i < len; i++) {
			for (int j = c; j > i + 1; j--) {
				a = i + 1;
				b = j - 1;
				if (nums[i] == nums[a] && nums[b] == nums[j] && b > a + 1) {
					c = j - 1;
					continue;
				}
				if (nums[b] == nums[j]) {
					--c;
				}
				while (b > a) {
					int sum = nums[i] + nums[a] + nums[b] + nums[j];
					while (sum > target && b > a + 1) {
						b--;
						sum = nums[i] + nums[a] + nums[b] + nums[j];
					}
					while (sum < target && b > a + 1) {
						a++;
						sum = nums[i] + nums[a] + nums[b] + nums[j];
					}
					if (sum == target) {
						List<Integer> param = new ArrayList<>();
						param.add(nums[i]);
						param.add(nums[a]);
						param.add(nums[b]);
						param.add(nums[j]);
						ans.add(param);
					}
					++a;
					--b;
				}
			}
		}
		return ans;
	}

	public static void main(String[] args) {
		Solution18 solution = new Solution18();
		System.out.println(solution.fourSum(new int[]{2, 2, 2, 2, 2}, 8));
		System.out.println(solution.fourSum(new int[]{1, 0, -1, 0, -2, 2}, 0));
		System.out.println(solution.fourSum(new int[]{-2, -1, -1, 1, 1, 2, 2}, 0));//不行 不做了
	}


}
